1. Field of the Invention
The present invention relates to computer network interfacing and switching and, more particularly, to an apparatus and method controlling a network switch port operating in a half-duplex mode.
2. Background Art
Local area networks use a network cable or other media to link stations on a network. Each local area network architecture uses a media access control (MAC) enabling network interfaces at each station to share access to a medium.
The Ethernet protocol (IEEE/ANSI Std. 802.3) defines a half-duplex media access format that permits all stations to access the network media channel with equality. Traffic is not distinguished or prioritized over the media. Each station includes an Ethernet interface that uses carrier-sense multiple-access with collision detection (CSMA/CD) to listen for traffic on the media. Any station can attempt to contend for the channel by waiting a predetermined transmission delay interval after the deassertion of the carrier on the media, known as the interpacket gap (IPG) interval. If a plurality of stations have data to send on the network, each of the stations will attempt to transmit in response to the sensed deassertion of the carrier on the media and after the IPG interval, resulting in a collision. Hence, a transmitting station will monitor the media to determine if there has been a collision due to another station sending data at the same time. If a collision is detected, both stations stop, wait a respective random amount of time, and retry transmission.
Ethernet networks mediate collisions by using a truncated binary exponential backoff (TBEB) algorithm, that provides a controlled pseudo-random mechanism to enforce a collision backoff interval before retransmission is attempted. According to the truncated binary exponential backoff algorithm, a station counts the number of transmission attempts (k) during the transmission of a current frame using a counter, referred to as a xe2x80x9cretry counterxe2x80x9d. The station computes a collision backoff interval as a randomized integer multiple of a slot time interval, and attempts retransmission after the collision backoff interval. The station will attempt to transmit under the truncated binary exponential algorithm until a maximum retry limit (kmax) has been reached. Under the Ethernet standard (IEEE/ANSI Std. 802.3), the maximum limit for retrying transmission of a data frame is sixteen (16) times. If the station unsuccessfully attempts transmission sixteen times, the data frame is discarded by the station.
The collision backoff interval is calculated by selecting a random number of time slots from the range of zero to 2k. For example, if the number of attempts is k=3, then the range of randomly selected integer multiples is (0,8); if the randomly-selected integer multiple is four, then the collision backoff interval will be equal to four slot time intervals. According to Ethernet protocol, the maximum range of randomly selected time slots is from zero to 210.
The truncated binary exponential algorithm has the disadvantage that the range of randomly selected integer multiples (0, 2k) increases exponentially each time a specific station unsuccessfully attempts a retry transmission after collision (i.e., the count k is increased), resulting in a higher probability that during the next collision mediation the station will randomly select a larger integer multiple of time slots, thereby decreasing the probability that the station will gain access to the media on the next retry transmission. Thus, a new station that has data to transmit has a higher probability of winning a collision mediation than the station having a greater number of attempts. This effect is known as the xe2x80x9ccapturexe2x80x9d effect, where a new station in the collision mediation effectively has a greater probability of capturing access to the media than the station attempting transmission prior to the new station.
Hence, collision mediation may reduce the network throughput and create unbounded packet access latencies. Consequently, the capture effect causes a large variance in the network access latency, and a corresponding large variance in end to end delays experienced by data packets.
Additionally, network stations generally do not have knowledge of the status of other stations on the network. If there is no collision, a transmitting station will transmit the data packet regardless of the state of the receiving station. If the receiving station is in a state of congestion, for example due to a lack of buffer space, the receiving station will discard the transmitted packet, resulting in a loss of data. If upper layer protocol requires the data to be resent, the sending station will resend the data packet at a later time, reducing the network throughput and efficiency.
Network congestion occurs if a receiving network element is unable to receive data at a rate greater than or equal to the transmission rate of the transmitting element. For example, traffic in a client-server environment is dominated by client requests followed by a burst of frames from the server to the requesting client. Although the full duplex environment enables the server to transmit packets while receiving requests from other clients, only a limited number of client requests can be output to the server from the switched hub at the assigned switching port. If the number of client requests exceeds the capacity of the server""s buffer, some of the data packets will be lost. Alternatively, a client having limited buffer space may be unable to keep up with the transmission rate of the server, resulting in lost packets.
Flow control has been proposed to reduce network congestion, where a receiving station causes a sending station to temporarily suspend transmission of data packets. A proposed flow control arrangement for a half duplex environment, referred to as xe2x80x9cbackpressurexe2x80x9d, directs a receiving station to force a collision with the transmitting station by transmitting a jamming sequence of bits when the receive buffer of the receiving station reaches a xe2x80x9creceive buffer unavailablexe2x80x9d state.
FIG. 7 illustrates the use of backpressure by a port 202 within a network switch 200 operating in half-duplex mode according to the CSMA/CD protocol. Port 202 receives and transmits data packets in communication with a network station 204 via a network media 206. If the port 202 is unsuccessful in transferring a data packet from its transmit buffer to the network station 204 over the media 206 due to collisions, the port 202 will backoff and wait a randomly selected period of time before retransmitting according to the CSMA/CD protocol. After each transmission attempt, the retry counter within the port is incremented. As discussed previously, as the number of retrys attempted by the transmitting port increases, the likelihood of that port gaining access to the media decreases.
Additionally, during the backoff interval, the receive buffers in port 202 may become active and start to receive a data packet 216 transmitted from network station 204. Should the receive buffers in the port 202 become overloaded due to congestion of the network switch bus 208 or other network ports 212, for example, the network switch engine 210 detects that the receive buffers of port 202 have become overloaded and directs the port to assert a backpressure jamming sequence 218, causing network station 204 to backoff and wait a randomly selected period of time before attempting retransmission.
Under the CSMA/CD protocol, the collision forced by the jamming sequence causes the transmitting network station 204 to abort, jam and retransmit a data packet after the collision backoff interval. Thus, the asserted xe2x80x9cbackpressurexe2x80x9d controls the input port congestion of station 202 by forcing the sending network station 204 to invoke the truncated binary exponential backoff (TBEB) algorithm under the CSMA/CD protocol. Consequently, the TBEB algorithm causes the sending station 204 to stop transmission and wait to retransmit when the collision backoff interval is complete. During the backoff interval, the congested port 202 is given time to unload its internal receive buffers. If the port 202 remains congested, additional backpressure is asserted onto network station 204 to attempt to further alleviate the port congestion.
Conditions giving rise to the assertion of backpressure by a port 202, such as congestion within the switch 200 and other ports 212 can cause degradation of the switch performance. In addition, a higher retry count value in ports asserting backpressure can lead to further performance degradation since these ports are less likely to gain access to the media. Hence, data packets awaiting retransmission remain in the transmit buffers for longer periods of time due to lost collision mediation, thereby aggravating the congestion in the switch.
There is a need for an apparatus and method for controlling a network switch port that provides the port a greater probability of gaining access to the media during collision mediation following the assertion of backpressure by that port, yet without exceeding the maximum allowable number of retry attempts prescribed by the Ethernet Standard.
This and other needs are attained by the present invention, where the retry counter of a network switch port is reset upon assertion of backpressure by the port to give the port a greater probability of winning collision mediation since the range of integers from which a random integer multiplier is selected under the CSMA/CD protocol is small due to a low k value. If the retry count value k is reset one or more times for the same frame, however, the total number of retry attempts may exceed the maximum allowable number dictated by the Ethernet standard (e.g., 16). This occurs because the retry count k is normally compared against an initial set value of kmax to determine when the maximum count is reached. Thus, adjustment of the value of kmax of retry attempts based upon the actual total number of retrys becomes necessary to ensure that the Ethernet standard is not violated. Hence, the present invention also adjusts the value of the maximum number of retry attempts (kmax) with each retry counter reset such that the total number of retrys will not exceed a maximum total number (e.g., the Ethernet standard of 16).
According to one aspect of the invention, a network switch in a computer network includes a plurality of ports configured for transferring data packets over the computer network. At least some of the plurality of ports have a retry counter that counts the number of occurrences that a respective port attempts and fails to transfer a data packet over the computer network. The count of the retry counter has a maximum retry limit value corresponding to a maximum number of times a respective port is currently allowed to attempt transfer of an individual data packet. Those ports having a retry counter also include a control logic for discarding an individual data packet in response to the count in the reset counter reaching the maximum retry limit value.
Furthermore, each the ports having a retry counter include a retry counter reset for resetting the count of the retry counter to a start value when a backpressure data sequence is asserted by the port onto the computer network. The retry counter reset affords the port a greater probability of winning collision mediation when the ports are attempting to transmit a data packet after backpressure assertion. In addition, the ports include a retry limit modification logic that modifies the maximum retry limit value after each assertion of backpressure by a respective port such that the total number of transfer attempts for any one individual data packet does not exceed a predetermined maximum total number of transfer attempts for the individual data packet (e.g., 16 as prescribed by the Ethernet Standard). Limiting the total number of transmission attempts for an individual data packet to a predetermined maximum total number ensures that the port will operate within the Ethernet Standard even though the retry count is reset after backpressure assertion.
According to another aspect of the invention, a method for controlling a port of a network switch in a computer network includes incrementing a count in a retry counter within the port each time the port attempts and fails to transfer a data packet over the computer network. The count of the retry counter has retry limit value corresponding to a maximum number of times the respective port is allowed to attempt transfer of an individual data packet. In addition, the method includes sensing whether a backpressure sequence of bits is transmitted by the port over the computer network. If exertion of backpressure is sensed, the count in the retry counter is reset to a start value. Further, the retry limit value of the count is modified each time the count is reset such that the total number of transfer attempts for an individual data packet does not exceed a maximum total retry limit. Limiting the total number of transmission attempts for an individual data packet to a maximum value ensures that the port operates within the Ethernet Standard even though the retry counter is reset subsequent to the assertion of backpressure.
Additional advantages and novel features of the invention will be set forth in part in the description which follows, and in part will become apparent to those skilled in the art upon examination of the following or may be learned by practice of the invention. The advantages of the invention may be realized and attained by means of the instrumentalities and combinations particularly pointed out in the appended claims.